The RC4 algorithm developed by RSA Data Security Inc. is an example of an encryption algorithm used for Internet web browsing. Prior to using the RC4 algorithm for encrypting data, a key setup process must be performed.
According to at least one wireless LAN security protocol, the key should be changed for every frame and key setup should be performed for every frame. Due the number of times key setup may be performed, reducing the key setup time may be important.
Also, at least one wireless LAN security protocol, allocates a fairly short time for building an encryption key and preparing a frame body. As an example, the 802.11g-OFDM wireless LAN security protocol allocates 12.5 μsec for building the encryption key and preparing the frame body.
A prior art system using a single finite state machine unit, a sequential architecture or a single port memory may require several clock cycles for data dependency and, as a result, it may become more difficult to set up the encryption key and prepare the frame body.
The RC4 algorithm uses a private key based on a stream cipher method. For ciphering the key and data, the RC4 algorithm may use a state table or “substitution box” (Sbox) for generating a pseudo-random number (PRN).
As shown in FIG. 1, the RC4 algorithm has three main steps or phases. The first step S100 is an initialization step in which the state table or Sbox is initialized. As shown in S100, address i and data S[i] are arranged in the Sbox. The Sbox may be initialized by setting each location equal to an index value. For example, for a 256 element array, for i=0 to 255, Sbox[i]=i. A second, key array of the same size may be filled with the key value, repeating bytes as necessary.
The second step S200, which may be referred to as “key setup”, generates permutations of the Sbox entries with a variable length key and stores them back into the Sbox. As shown in FIG. 1, S200 is step for performing key setup 256 times by performing new key shuffling (or swapping) in the Sbox having 256 entries. An example of the second, key setup step S200 follows.
for i=0 to 255:j=(K[k] + Sbox[i] + j) mod 256;swap (&Sbox[i], Sbox[j]);k=(k+1).
The Sbox may now contain random permutations of its original entries. Further, the Sbox may evolve with use. The index i may ensure that every entry changes and the index j may ensure that the entries change randomly.
Describing the key setup in more detail, in a first step, certain variables and the indexes i and j are initialized. The variable k is used later during a swapping step. In a next step, the RC4 permutation calculation is performed. The permutation calculation may be performed according to:j=(K[k]+Sbox[i]+j)mod 256.
In the first iteration, k=Sbox[0]. However, in subsequent iterations, k is equal to sbox_next_i, which may be Sbox[i+1].
In a next step, Sbox[i] is set to Sbox[j] and Sbox[j] is set to Sbox[i+1]. In an example hardware implementation, an Sbox register may be used to facilitate the swapping function.
At a next step, the index i is incremented and the algorithm is repeated until the index i is greater than 255. It is understood by those of skill in the art that the loop is not necessarily repeated 256 times, but that the value of i is determined by the size of the Sbox and that the modulo arithmetic also depends on the size of the Sbox.
As shown in FIG. 1 and described above, step S200 may include multiple read or write operations, for example, four (4) read or write operations. These may include reading S[i] in the i-th address of the Sbox, reading S[j] in the j-th address of the Sbox, writing S[i] in the j-th address of the Sbox, and writing S[j] in the i-th address. If the Sbox is a single port memory, for example, a single port SRAM, four (4) clock cycles are required for to perform the key setup.
In a third message processing or “data ciphering” step S300, random Sbox entries may be used to either convert a message to cipher text or recreate a message from cipher text. Example pseudo code for the data ciphering” step S300, in which a message is converted to cipher text follows.
i=j=0;for each byte of the message,repeati=(i+1) mod 256;j=(Sbox[i]+j) mod 256;swap (&Sbox[i], Sbox[j]);x=(Sbox[i]+Sbox[j]) mod 256;Dout=Din ⊕ S[x];end.
Describing the data ciphering in more detail, in a first step, similar to the key setup, certain variables and the indexes i and j are initialized. That is, indices i and j are set to zero. In a next step, standard RC4 processing calculations are performed, followed by a swapping step. The standard RC4 processing calculations may set the index i equal to ((i+1) mod 256) and the index j equal to ((j+k) mod 256). In the swapping step, Sbox[i] is set to Sbox[j] and Sbox[j] is set to Sbox[i]. As in the key setup, a Sbox register may be used to facilitate the swapping function.
Next, a pseudo-random byte is determined in accordance with the RC4 algorithm. That is, x=(Sbox[i]+Sbox[j]) mod 256. Next, a byte of the cipher text may be generated by exclusive ORing (XORing, for example) a byte of the message with the pseudorandom byte from the Sbox, i.e., Sbox[x].
In a decrypting process, a byte of the cipher text may be XORed with the pseudo-random Sbox byte to recreate a byte of the message. Next, a step may be performed, which checks to determine whether or not j is equal to i+1. If j is not equal to i+1, then the variable K is equated to Sbox[i+1]. Alternatively, if j is equal to i+1, then if the last byte of the message has not yet been processed, the algorithm is repeated by looping back.
FIG. 2 is an example illustrating the limited time allotted for performing key setup. The example of FIG. 2 illustrates the communications between a MAC (Media Access Control) controller and a modem, for an 802.11g 54 Mbps transmission running the RC4 algorithm with an integrity check. As illustrated in FIG. 2, the MAC controller transmits a transmit enable (TX ENABLE) signal to the modem. In response, the modem transmits a transmit ready (TX READY) signal and a transmit clock (TX CLOCK) signal to the MAC controller. As shown, the TX CLOCK signal includes burst clocks having a symbol time of 4 μseconds.
During the burst clocks, the MAC controller transmits data (TX DATA) to the modem. As shown in FIG. 2, the TX DATA may include rate (RATE) data, which indicates a rate of a transmitted frame, length (LEN) data, which indicates a length of the transmitted frame, header (HDR) data which indicates a header of the transmitted frame, and a body (BDY) of the transmitted frame.
The key setup time may be defined as the time period from the issuance of the TX ENABLE signal by the MAC controller to the transmission of the body of the transmitted frame BDY by the MAC controller. As indicated above, for an 802.11g 54 Mbps transmission, the maximum allowed key setup time may be on the order of 12.5 μseconds. This key setup time is characteristic of several 802.11 WLAN key setup times, for example 802.11a or 802.11g.
Conventional architectures may include one or more multiport memories operating in conjunction with a single, sequential architecture, finite state machine unit. However, sequential architectures and/or single finite state machine unit may not enable sufficient reduction of the key set-up time. Additionally, such architectures may be unsuitable for wireless communications because they may store the key in an external memory and/or may not change the key for every frame.